Optimized Resolvent Splitting Examples¶
This notebook generates the figures in our paper, which outlines the use of a semi-definite programming framework for optimizing splitting algorithms which solve the following monotone inclusion problem:
\begin{equation} 0 \in \sum_{i=1}^{n} A_{i}(x). \end{equation}
It does so by finding valid matrices $L$ and $W$ for the following set of iterations, where bolded entries are lifted, i.e. $\mathrm{x} = (x_1, \dots, x_n)$:
\begin{align} \mathrm{x} &= J_{\mathrm{A}}\left(\mathrm{v}^{k} + \mathrm{L} \mathrm{x}\right)\\ \mathrm{v}^{k+1} &= \mathrm{v}^{k} - \gamma \mathrm{W} \mathrm{x}. \end{align}
$L$ is lower diagonal, so we work with a symmetrized matrix $Z = 2I - L - L^T$
import numpy as np
import oars
from oars.matrices import *
from oars.utils import *
from oars.pep import *
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
# matplotlib.use('nbagg')
import seaborn as sns
sns.set()
from matplotlib.colors import CenteredNorm
import cvxpy as cvx
from collections import defaultdict
!mkdir -p figs
Our first example builds the matrices, which can be thought of as the graph Laplacians of communication graphs for the nodes in a distributed setting, to avoid specific communication paths.
We suppose a set of two clusters (0-2) and (3-5) which can only communicate within clusters and via a link between 0-3.
We then plot a Gantt chart for the distributed execution of the resulting algorithm.
We take as our objective function here the spectral norm of $Z-W$, which promotes graph similarity.
# Data for matrices in cluster example (6x6)
n = 6
Z_fixed = {(r,c):0 for r in range(4,6) for c in range(3)}
Z_fixed[(3,1)] = 0
Z_fixed[(3,2)] = 0
Z, W = getSimilar(n, fixed_Z=Z_fixed, fixed_W=Z_fixed)
# Figure 3
t = 0.016*np.ones(n)
l = 0.00025*np.ones((n, n))
l[0, 3] = 0.01
l[3, 0] = 0.01
fig = getGantt(t, l, Z, W, title="Cluster Algorithm Parallelism", itrs=5)
fig.show()
fig.write_image("figs/fig_gantt.pdf")
In this example, we visually depict the different matrices generates by changing the objective function between maximizing algebraic connectivity, minimizing SLEM, minimizing total effective resistance, and minimizing the spectral norm of the difference of the matrices.
We also demonstrate the use of the getBlockMin function to build the constraint set for the SDP to guarantee that the nodes can execute in blocks. If the compute and communication times are constant and uniform, this guarantees that the algorithm can execute with the highest possible degree of parallelism possible for this type of splitting.
# Figure 4 helper
def cplot(W,Z):
vmin = np.floor(np.min(np.minimum(W, Z)))
cm = plt.cm.coolwarm
fig, ax = plt.subplots(1, 2, figsize=(12, 6))
x = -np.arange(n)
y = np.arange(n)
ax[0].pcolormesh(x, y, W, norm=CenteredNorm(), cmap=cm) #, vmin=vmin, vmax=2)
ax[0].set_title(r"$W$")
ax[0].axis('off')
ax[0].set_aspect('equal')
pc = ax[1].pcolormesh(x, y, Z, norm=CenteredNorm(), cmap=cm)
ax[1].set_title(r"$Z$")
ax[1].axis('off')
ax[1].set_aspect('equal')
# Add colorbar
plt.tight_layout()
fig.colorbar(pc, ax=ax.ravel().tolist())
return fig
# Figure 4
n = 10
m = 2
Z, W = getBlockMin(n, m, objective=getMaxConnectivity)
fig = cplot(W, Z)
# Save as pdf
fig.savefig("figs/fig_block_fiedler.pdf")
# Figure 4
Z, W = getBlockMin(n, m, objective=getMinSLEM)
fig = cplot(W, Z)
fig.savefig("figs/fig_block_slem.pdf")
# Figure 4
Z, W = getBlockMin(n, m, objective=getMinResist)
fig = cplot(W, Z)
fig.savefig("figs/fig_block_resist.pdf")
# Figure 4
Z, W = getBlockMin(n, m, objective=getSimilar)
fig = cplot(W, Z)
fig.savefig("figs/fig_block_lw.pdf")
This example shows a comparison of the execution of the block designs when the computation times are not uniform, and the use of the getMinCycle function to generate designs which minimize the iteration time.
# Figure 5 (hangs if executed in Windows using Kaleido 0.1.0post1)
# try pip install kaleido==0.1.0post1
n = 6
t = np.ones(n)
l = np.ones((n,n))/10
t[0] = 6
t[2] = 6
t[3] = 6
for i in range(1, n//2+1):
Zb, Wb = getBlockMin(n, i, objective=getMinResist)
if i == 1:
itrs = 6
else:
itrs = 7
fig = getGantt(t, l, Zb, Wb, title=str(n//i)+"-Block", itrs=itrs)
fig.write_image("figs/fig_misdp"+str(n//i)+"block.pdf")
fig.show()
Z, W = getMinCycle(n, t=t, l=l, objective=getMinResist)
fig = getGantt(t, l, Z, W, title="Minimum Iteration", itrs=12)
fig.write_image("figs/fig_misdp_min_cycle.pdf")
fig.show()
In several of the following examples, we use the PEP formulation to find the contraction factor for the algorithm designs in two scenarios:
$(n)$ 2-Lipschitz 1-strongly monotone operators
$(n-1)$ 2-Lipschitz 1-strongly monotone operators, and 1 unrestricted maximal monotone operator (this simulates having the subdifferential of an indicator function over some convex set)
In the figure 6 example, we use a fixed step size of 0.5.
We then compare the different algorithm designs, including the spectral objectives using our SDP, and some existing designs in the literature.
# Figure 6 - contraction rate results
# fig_smoothstronglyconvex.ipynb
# Function to generate list of all test matrices
def getTestMatrices(n):
cases = []
Ws = []
names = ['Full', 'MT']
Lf, Wf = getFull(n)
Mf = getMfromWCholesky(Wf)
cases.append((Lf, Mf))
Ws.append(Wf)
Lmt, Wmt = getMT(n)
Mmt = getMfromWCholesky(Wmt)
cases.append((Lmt, Mmt))
Ws.append(Wmt)
i = n//2
for obj in [getMinSLEM, getMinResist, getMaxConnectivity]:
L, W = getBlockMin(n, i, objective=obj)
M = getMfromWCholesky(W)
cases.append((L, M))
Ws.append(W)
title = f"2-Block "+ obj.__name__
names.append(title)
return cases, names, Ws
def getMatrixContraction(cases, names, Lc=2, mu=1, gamma=0.5):
'''Get contraction factors for matrix cases
Args:
cases (list): list of cases with L and M
names (list): list of names
Lc (float): Lipschitz constant
mu (float): strong convexity parameter
gamma (float): step size
Returns:
taus (dict): dictionary of contraction factors
'''
taus = {}
for i, (L, M) in enumerate(cases):
n = L.shape[0]
ls = np.ones(n)*Lc
mus = np.ones(n)*mu
tau, _ = getReducedContractionFactor(L, M, ls, mus)
taus[names[i]] = tau
print(names[i], tau)
return taus
# Figure 6 helper
def testFixedRate(start=4, end=31, lc=2, mc=1):
tau_results = defaultdict(list)
for n in range(start, end, 2):
print(f"Testing optimal rate on {n} nodes")
ls = np.ones(n) * lc
mus = np.ones(n) * mc
cases, names, Ws = getTestMatrices(n)
for i, (L, M) in enumerate(cases):
tau = getReducedContractionFactor(L, M, ls, mus)
tau_results[names[i]].append(tau)
# Convert results to df
tau_df = pd.DataFrame(tau_results)
tau_df.index = range(start, end, 2)
return tau_df
# Figure 6a
tau_df = testFixedRate(start=6, end=31)
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
# Plot figure 6a
fig, ax = plt.subplots()
tau_df.plot(ax=ax)
ax.set_xlabel("n")
ax.set_ylabel("Contraction")
ax.set_title(r"Fixed step size contraction with $n$ Lipschitz strongly monotone operators")
ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc=(0.25,0.4))
fig.savefig("figs/fig6a.pdf", format="pdf", bbox_inches="tight")
# Figure 6b helper
def testFixedRateProj(start=4, end=31, lc=2, mc=1):
tau_results = defaultdict(list)
for n in range(start, end, 2):
print(f"Testing optimal rate on {n} nodes")
ls = np.ones(n) * lc
ls[n-1] = np.inf
mus = np.ones(n) * mc
mus[n-1] = 0
cases, names, Ws = getTestMatrices(n)
for i, (Z, M) in enumerate(cases):
tau = getReducedContractionFactor(Z, M, ls, mus)
tau_results[names[i]].append(tau)
# Convert results to df
tau_df = pd.DataFrame(tau_results)
tau_df.index = range(start, end, 2)
return tau_df
# Figure 6b
tau_df = testFixedRateProj(start=6, end=31)
Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
# Plot figure 6b
fig, ax = plt.subplots()
tau_df.plot(ax=ax)
ax.set_xlabel("n")
ax.set_ylabel("Contraction")
ax.set_title("Fixed step size contraction with an unrestricted monotone operator")
ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc="lower right")
fig.savefig("figs/fig6b.pdf", format="pdf", bbox_inches="tight")
In figure 7 we repeat the analysis, but using an optimal step size we derive from an extension of the dual of the PEP. This also demonstrates the use of the getReducedGamma function, which generates a step size which minimizes the contraction factor for the reduced version of the algorithm:
\begin{align} \mathrm{x} &= J_{\mathrm{A}}\left(-\mathrm{M}^{T} \mathrm{z}^{k} + \mathrm{L} \mathrm{x}\right)\\ \mathrm{z}^{k+1} &= \mathrm{z}^{k} + \gamma \mathrm{M} \mathrm{x}. \end{align}
where $M^T M = W$
# Figure 7 helper
def testOptimalRate(start=4, end=31, lc=2, mc=1):
tau_results = defaultdict(list)
for n in range(start, end, 2):
print(f"Testing optimal rate on {n} nodes")
ls = np.ones(n) * lc
ms = np.ones(n) * mc
cases, names, Ws = getTestMatrices(n)
for i, (Z, M) in enumerate(cases):
_, tau = getReducedGamma(Z, M, ls, ms)
tau_results[names[i]].append(tau)
# Convert results to df
tau_df = pd.DataFrame(tau_results)
tau_df.index = range(start, end, 2)
return tau_df
# Figure 7 helper
def plotTau(tau_df, title):
fig, ax = plt.subplots()
tau_df.plot(ax=ax)
ax.set_xlabel("n")
ax.set_ylabel("Contraction") #$\\tau$
ax.set_title(title)
ax.legend(['Full', 'MT', '2-Block Min SLEM', r'2-Block Min Resistance (also min $\|Z-W\|$)', '2-Block Max Fiedler'], loc="center right")
#ax.legend(loc='center right')
#plt.show()
return fig
# Figure 7
tau_df = testOptimalRate(start=4, end=31)
tau_df.to_csv("figs/fig_opt_gamma_strong.csv", index=False)
Testing optimal rate on 4 nodes No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
# Figure 7
#tau_df = pd.load_csv("fig_opt_gamma_strong.csv")
fig = plotTau(tau_df, "Contraction over $n$ Lipschitz strongly monotone operators")
fig.savefig("figs/fig_opt_gamma_strong.pdf", format="pdf", bbox_inches="tight")
# Figure 7 helper
def testOptimalRateProj(start=4, end=31, lc=2, mc=1):
tau_results = defaultdict(list)
for n in range(start, end, 2):
print(f"Testing optimal rate on {n} nodes")
ls = np.ones(n) * lc
ls[n-1] = np.inf
mus = np.ones(n) * mc
mus[n-1] = 0
cases, names, Ws = getTestMatrices(n)
for i, (Z, M) in enumerate(cases):
_, tau = getReducedGamma(Z, M, ls, mus)
tau_results[names[i]].append(tau)
# Convert results to df
tau_df = pd.DataFrame(tau_results)
tau_df.index = range(start, end, 2)
return tau_df
# Figure 7b
tau_df = testOptimalRateProj(start=4, end=31)
tau_df.to_csv("figs/fig_opt_gamma_proj.csv", index=False)
Testing optimal rate on 4 nodes No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 6 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
# Figure 7b
fig = plotTau(tau_df, "Contraction with an unrestricted monotone operator")
fig.savefig("figs/fig7b.pdf", format="pdf", bbox_inches="tight")
In figure 8 we examine the impact of operator ordering on the contraction factor. In this example (and previous ones), we illustrate the use of some of the prebuilt matrix functions.
getMT(n) returns the Malitsky-Tam algorithm design over $n$ operators
getRyu(n) returns the Tam extension of the Ryu algorithm design over $n$ operators
getFull(n) returns the fully connected algorithm with equal weights over $n$ operators
We also use a helper function getMfromWCholesky to return a valid $M \in \mathbf{R}^{n-1 \times n}$ such that $M^T M = W$
# Figure 8 - operator ordering
Lc=2
mu=1
taus = defaultdict(list)
for n in range(4, 31, 2):
print(f"Testing optimal rate on {n} nodes")
Lb, Wb = getBlockMin(n, n//2)
Mb = getMfromWCholesky(Wb)
Lmt, Wmt = getMT(n)
Mmt = getMfromWCholesky(Wmt)
Lr, Wr = getRyu(n)
Mr = getMfromWCholesky(Wr)
Lmax, Wmax = getFull(n)
Mmax = getMfromWCholesky(Wmax)
cases = [(Lb, Mb), (Lmt, Mmt), (Lr, Mr), (Lmax, Mmax)]
names = ["2-Block", "MT", "Ryu", "Full"]
ls = np.ones(n)*Lc
ls[n-1] = np.inf
mus = np.ones(n)*mu
mus[n-1] = 0
for i, (Z, M) in enumerate(cases):
_, tau = getReducedGamma(Z, M, ls, mus)
taus[names[i]].append(tau)
ls = np.ones(n)*Lc
ls[0] = np.inf
mus = np.ones(n)*mu
mus[0] = 0
for i, (Z, M) in enumerate(cases):
_, tau = getReducedGamma(Z, M, ls, mus)
taus[names[i]+" reverse"].append(tau)
Testing optimal rate on 4 nodes No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 6 nodes No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 8 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 10 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 12 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 14 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 16 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 18 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 20 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 22 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator Testing optimal rate on 24 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 26 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 28 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
Testing optimal rate on 30 nodes
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
# Figure 8 - operator ordering
df = pd.DataFrame(taus)
df.index = range(4, 31, 2)
# Plot the results
colors = ['blue', 'green', 'red', 'purple']
styles = ['b-', 'g-', 'k-', 'm-', 'y--', 'c--', 'r--', 'p--']
styles = ['b-', 'g-', 'k-', 'm-', 'b*-', 'g*-', 'k*-', 'm*-']
df.to_csv("figs/fig_function_ordering_opt.csv", index=False)
df.plot(style=styles)
plt.xlabel("Number of nodes")
plt.ylabel("Contraction")
plt.title("Operator Ordering and Splitting Performance")
plt.savefig("figs/fig_function_order_opt.pdf", format="pdf", bbox_inches="tight")
plt.show()
Figure 9 examines the impact of block count in the $d$-Block designs on the reduced contraction factor.
# Figure 9 - block size
# See 04_23_24_block_size.ipynb
# Function to generate list of all test matrices
def getTestMatricesBlocks(n):
cases = []
names = ['Full', 'MT']
objs = ['Full', 'MT']
blocksizes = ['', '']
blocklist = ['', '']
Lf, Wf = getFull(n)
Mf = getMfromWCholesky(Wf)
cases.append((Lf, Mf))
Lmt, Wmt = getMT(n)
Mmt = getMfromWCholesky(Wmt)
cases.append((Lmt, Mmt))
objstring = ['MinSLEM', 'MinResist', 'getMaxConnectivity', 'Min |Z-W|']
for i in range(2, n//2+1):
if n % i != 0:
continue
for j, obj in enumerate([getMinSLEM, getMinResist, getMaxConnectivity, getSimilar]):
L, W = getBlockMin(n, i, objective=obj)
M = getMfromWCholesky(W)
cases.append((L, M))
objs.append(objstring[j])
blocksizes.append(i)
blocklist.append(n//i)
title = f"{n//i}-Block "+objstring[j]
names.append(title)
return cases, names, objs, blocksizes, blocklist
# Test function
def testMatrices(cases, names, lc=2, mu=1, gamma=0.5):
taus = {}
for i, (L, M) in enumerate(cases):
ls = np.ones(len(L))*lc
mus = np.ones(len(L))*mu
gamma, tau = getReducedGamma(L, M, ls, mus)
print(names[i], tau)
taus[names[i]] = tau
return taus
# Figure 9
results = []
for n in range(4, 25): #t < 120:
print(n)
cases, names, objs, blocksizes, blocks = getTestMatricesBlocks(n)
taus = testMatrices(cases, names)
# Each key in taus is a column, the row is the value of n
for i in range(len(names)):
k = names[i]
v = taus[k]
results.append({"n": n, "name": k, "obj": objs[i], "blocksize": blocksizes[i], "blocks":blocks[i], "tau": v})
df = pd.DataFrame(results)
# Save to csv
df.to_csv("figs/taus_plus.csv", index=False)
df.set_index('n', inplace=True)
4
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4275726424387023 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.8002281453197694 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571563320386254 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.4285714308439043 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.47232795740698197 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.42857142974429335 5 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.44769222096754585 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.861371784044431 6
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.45925820423443237 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.8973983347682633 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.7135742120391384 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinResist 0.7182631442291072 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7125769076136125 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7146237387666267 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562848351927 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.4285714345044546 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.488471357684012 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.4285714294945974 7 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.46675734145403897 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.921028546326316 8
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.47200715470169324 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9373167138798217 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.8309037714895217 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinResist 0.8108953220221728 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.8002349980331156 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9414775041859474 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562864004128 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.4285714324225226 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.49712977590980384 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285717289200378 9
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.47588407918368214 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9490542144439524 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.7139323261601181 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinResist 0.7182631341824306 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7138583593905867 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7154479936264707 10
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4788623869914284 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9578086304484562 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.8909710630474715 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinResist 0.867517704847014 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block getMaxConnectivity 0.8694665060801878 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.8841704218835689 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562868119515 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714375496707 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5007530033260064 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.4285714341244909 11 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.48122091775576264 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9645090300427932 12
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.48313426706054324 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9697458591679796 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9274863710223136 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinResist 0.9043223463150312 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block getMaxConnectivity 0.914435584101685 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9723014749721509 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.8306040572340888 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinResist 0.8108995469244207 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.8002317783831558 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9732200751675371 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.713882481243341 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631630830676 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.715230555842219 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7154244052497442 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562881070227 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.4285714382736276 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5048840996026825 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857143401716014 13 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.48471718030960137 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9739133518549759 14
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4860481904482536 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9772819066072161 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinSLEM 0.9487402271176432 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinResist 0.927596295234003 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9415108626363436 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block Min |Z-W| 0.9379760462197118 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.55715631881924 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.4285714451273485 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5053543651074622 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857144536092834 15
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4871828194233909 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9800422357401884 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.8909885842670557 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.8675200794190076 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block getMaxConnectivity 0.8694664535695544 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.8841748808659018 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.714146321224925 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631419821576 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7151833903650163 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7154940849150406 16
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4881613958305955 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9823315596735169 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block MinSLEM 0.9617907227701468 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.943201687354377 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block getMaxConnectivity 0.9547829224265896 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block Min |Z-W| 0.9843154256403905 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.8304099808829254 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108998689438812 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.8002305076130293 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9847811629257821 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562810344565 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714541891736 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5061192607260824 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.42857145632199684 17 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4890140016796066 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9842506483710652 18
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4897634138975941 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9858748663020437 No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinSLEM 0.9703808977320246 No operators provided, using default LipschitzStronglyMonotoneOperator 9-Block MinResist 0.9543244267153969 No operators provided, using default LipschitzStronglyMonotoneOperator 9-Block getMaxConnectivity 0.9652620352983484 No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block Min |Z-W| 0.9609559413334392 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9274863340035625 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinResist 0.9043221002381561 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.9144368470087124 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block Min |Z-W| 0.9877641370603041 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.7137591263162248 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631394318443 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7156777756433123 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7151300240640917 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.5571562751598028 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.42857145889845066 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5065757351760865 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.4285714592806289 19 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.49042725685598193 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9872613997715868 20
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4910193660443159 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9884542931847442 No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinSLEM 0.9764918849308651 No operators provided, using default LipschitzStronglyMonotoneOperator 10-Block MinResist 0.9624236294978088 No operators provided, using default LipschitzStronglyMonotoneOperator 10-Block getMaxConnectivity 0.9726910272407457 No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block Min |Z-W| 0.9899039312877368 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.8909604944000604 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinResist 0.8675196430955869 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.8694657973899463 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.8841780055879428 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinSLEM 0.8306547100590185 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinResist 0.8108995981763438 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block getMaxConnectivity 0.8002314011892808 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9902135583212976 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562921308054 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.42857146164360865 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5073479525629142 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.42857146229032794 21
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4915507533342906 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9894878242816122 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9487432478204636 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinResist 0.9275962670135205 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block getMaxConnectivity 0.9415190793066045 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9379767047546463 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.7135615903063515 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631426600574 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7154026658832751 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.7151513652545484 22
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.4920302859111904 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9903890671244222 No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinSLEM 0.980965610573116 No operators provided, using default LipschitzStronglyMonotoneOperator 11-Block MinResist 0.9685141496041315 No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block getMaxConnectivity 0.9778676566839088 No operators provided, using default LipschitzStronglyMonotoneOperator 11-Block Min |Z-W| 0.9734129802157969 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562777402097 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714662419582 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.509139759936115 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.4285714662517721 23 No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.49246519297458935 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9911795563987065 24
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.49286136387228907 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9918767125507102 No operators provided, using default LipschitzStronglyMonotoneOperator 12-Block MinSLEM 0.9842233175864209 No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinResist 0.9732178088466078 No operators provided, using default LipschitzStronglyMonotoneOperator 12-Block getMaxConnectivity 0.9816646293348918 No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block Min |Z-W| 0.9929855588536252 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block MinSLEM 0.9617899149115514 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.9432016721396277 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block getMaxConnectivity 0.9547828415390756 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9930940221228003 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9274864211025259 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9043224063558409 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block getMaxConnectivity 0.9144367580557783 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9931276194911502 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.8310241286149925 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.8108982477568355 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.8002305222419616 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9931862824296942 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.7139332118231382 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.7182631402120128 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.7152482065411033 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.7152800293177907 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.5571562808428404 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.4285714310144412 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.5099386151008687 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.42857147069365215
df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].groups.keys()
dict_keys([('Full', ''), ('MT', ''), ('MinResist', 2), ('MinResist', 3), ('MinResist', 4), ('MinResist', 5), ('MinResist', 6), ('MinResist', 7), ('MinResist', 8), ('MinResist', 9), ('MinResist', 10), ('MinResist', 11), ('MinResist', 12)])
# Figure 9
# Load taus.csv
#df = pd.read_csv("taus.csv")
#df.loc[df['name'].isin(['Full', 'MT']), ['blocks', 'blocksize']] = ''
df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].plot(marker='o', linestyle='-', figsize=(10, 6))
keys = df[df["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].groups.keys()
keys = ['Full', 'MT', '2-Block', '3-Block', '4-Block', '5-Block', '6-Block', '7-Block', '8-Block', '9-Block', '10-Block', '11-Block', '12-Block']
plt.legend(keys, bbox_to_anchor=(1, 1))
# Make x axis integer
plt.xticks(np.arange(4, 25, 2))
plt.xlabel(r"$n$")
plt.title("Min Resistance Contraction over $n$ Lipschitz Strongly Monotone Operators by Block Number")
plt.savefig("figs/fig_block_count.pdf", format="pdf", bbox_inches="tight")
# Figure 9 - Test function
def testMatricesProj(n, cases, names, lc=2, mu=1):
ls = np.ones(n)*lc
mus = np.ones(n)*mu
ls[n-1] = np.inf
mus[n-1] = 0
taus = {}
for i, (Z, M) in enumerate(cases):
gamma, tau = getReducedGamma(Z, M, ls, mus)
print(names[i], tau)
taus[names[i]] = tau
return taus
# Figure 9
projresults = []
for n in range(4,26): #t < 120:
print(n)
cases, names, objs, blocksizes, blocks = getTestMatricesBlocks(n)
taus = testMatricesProj(n, cases, names)
# Each key in taus is a column, the row is the value of n
for i in range(len(names)):
k = names[i]
v = taus[k]
projresults.append({"n": n, "name": k, "obj": objs[i], "blocksize": blocksizes[i], "blocks":blocks[i], "tau": v})
projdf = pd.DataFrame(projresults)
projdf.to_csv("figs/taus_proj.csv", index=False)
projdf.set_index('n', inplace=True)
4
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.7521521274547772 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9177841369745814 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.8191387832657023 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.7870338922103205 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.8005884142677305 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.7870338929300077 5 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.8044792127888197 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9475773165769197 6
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.838558740668551 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.963679040723567 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.9045196638648727 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinResist 0.8989263093339976 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9031665201664806 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.905811564931693 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.8708680920365564 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.8616700832103537 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.8648381115704538 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.8616700813867951 7 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.8625324131656744 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9733944272799456 8
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.8803148080938116 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9796953548701708 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.947737890434155 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinResist 0.9366150047051096 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.9409068724807719 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9733653867324151 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.899665656605118 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.897358435818429 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.897061358320355 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.8973584363622054 9
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.8940287042166419 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9840061423604513 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.9310037419763251 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinResist 0.9226238048816924 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9308683371509562 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.9329235479910636 10
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.904926183461662 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9870820594200824 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.9690123429432841 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinResist 0.9580312775913491 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block getMaxConnectivity 0.9629973163283422 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.9629875076136046 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.9180267565103261 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9183673760071706 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.916691539095593 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.9183673754845947 11 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9137934450814554 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9893521326451261 12
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9211491280506094 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9910743537751981 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9794372274110801 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinResist 0.9701555310266454 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block getMaxConnectivity 0.9756973937657129 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9901053735796335 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.9594826252987537 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinResist 0.9489711986480376 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.9564324332772989 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9875641251533125 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.946111764232151 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9376136641003235 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9476885966472107 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.9478983876149142 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.9307344399512485 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.9322246586548181 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9300141945007564 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9322246586787853 13 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9273491859704499 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9924113648329533 14
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9326458422577715 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9934697819644993 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinSLEM 0.9854895183964308 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinResist 0.9778942636533086 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block getMaxConnectivity 0.9826255558805462 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block Min |Z-W| 0.9813969436642211 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.9400431051319559 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.9420552244966905 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.93962997966507 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9420552246279524 15
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9372231868414823 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9943217922541321 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.9745905142273118 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.9649800729638587 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block getMaxConnectivity 0.97109604331107 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.9698496425926824 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.9561864907269577 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9478753095788607 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9572607197812847 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.9575677751837032 16
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9412182809698143 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9950176830139388 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block MinSLEM 0.9892332894570556 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.9829428678594524 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block getMaxConnectivity 0.9871235320735171 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block Min |Z-W| 0.9951900483795266 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.9674712824239583 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9575260017395849 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.9660343274443299 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9928356727270506 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.9471521763588401 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.949393105826944 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9469224619296801 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block Min |Z-W| 0.9493931076789771 17 No operators provided, using default LipschitzStronglyMonotoneOperator
Full 0.9447354996210365 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9955932803543736 18
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9478557853408256 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9960747909750525 No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block MinSLEM 0.9917523264434918 No operators provided, using default LipschitzStronglyMonotoneOperator 9-Block MinResist 0.9865001993504064 No operators provided, using default LipschitzStronglyMonotoneOperator 9-Block getMaxConnectivity 0.9901485319734604 No operators provided, using default LipschitzStronglyMonotoneOperator
9-Block Min |Z-W| 0.9891810856357947 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9825424907370934 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinResist 0.9744372782099368 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block getMaxConnectivity 0.980233378159765 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block Min |Z-W| 0.9955573342108432 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.962597375900911 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9552965512071064 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9643509557600238 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.9639152809238458 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9527572967367743 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.9550802030838836 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9526415889172174 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9550802035807927 19 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9506426888675972 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9964816118850218 20
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9531469126958877 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.996828412190169 No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block MinSLEM 0.9933657727548645 No operators provided, using default LipschitzStronglyMonotoneOperator 10-Block MinResist 0.989021596451965 No operators provided, using default LipschitzStronglyMonotoneOperator 10-Block getMaxConnectivity 0.9922094089430822 No operators provided, using default LipschitzStronglyMonotoneOperator
10-Block Min |Z-W| 0.997249101000427 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.9784207691778445 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinResist 0.970002773290226 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block getMaxConnectivity 0.9767083047982691 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block Min |Z-W| 0.9748735391998931 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.9721920253364399 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9637516383755966 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.9724249952213602 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block Min |Z-W| 0.9953488150061929 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.957289303111209 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.9596176455084063 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9572470127193968 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9596176491751938 21
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9554093767969893 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.997126427183303 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block MinSLEM 0.9874743349656987 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block MinResist 0.9805966853358046 No operators provided, using default LipschitzStronglyMonotoneOperator 7-Block getMaxConnectivity 0.9859614173482282 No operators provided, using default LipschitzStronglyMonotoneOperator
7-Block Min |Z-W| 0.9837394037231179 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.9674384858366795 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinResist 0.9608952673738462 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block getMaxConnectivity 0.9689905904689212 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block Min |Z-W| 0.9688040622204398 22
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9574634693504176 No operators provided, using default LipschitzStronglyMonotoneOperator MT 0.9973843798884913 No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block MinSLEM 0.9945861395582486 No operators provided, using default LipschitzStronglyMonotoneOperator 11-Block MinResist 0.990885042528622 No operators provided, using default LipschitzStronglyMonotoneOperator
11-Block getMaxConnectivity 0.9936950430727856 No operators provided, using default LipschitzStronglyMonotoneOperator 11-Block Min |Z-W| 0.993050008194392 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinSLEM 0.9610289962695392 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinResist 0.9633222012559908 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9610325830709481 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9633222012848819 23 No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9593367015363936 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9976091357279269 24
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9610519693853622 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9978061502088273 No operators provided, using default LipschitzStronglyMonotoneOperator 12-Block MinSLEM 0.9954966157859618 No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block MinResist 0.992309516634275 No operators provided, using default LipschitzStronglyMonotoneOperator 12-Block getMaxConnectivity 0.9947938451726746 No operators provided, using default LipschitzStronglyMonotoneOperator
12-Block Min |Z-W| 0.998250279297009 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block MinSLEM 0.9904306534939393 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block MinResist 0.984760973185923 No operators provided, using default LipschitzStronglyMonotoneOperator 8-Block getMaxConnectivity 0.9894469771429388 No operators provided, using default LipschitzStronglyMonotoneOperator
8-Block Min |Z-W| 0.9978752519029023 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block MinSLEM 0.9855261836489811 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block MinResist 0.9776570058925739 No operators provided, using default LipschitzStronglyMonotoneOperator 6-Block getMaxConnectivity 0.9841645885838068 No operators provided, using default LipschitzStronglyMonotoneOperator
6-Block Min |Z-W| 0.9974805118721081 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block MinSLEM 0.9756430702194357 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block MinResist 0.9684466642077201 No operators provided, using default LipschitzStronglyMonotoneOperator 4-Block getMaxConnectivity 0.976317381794523 No operators provided, using default LipschitzStronglyMonotoneOperator
4-Block Min |Z-W| 0.9967388078611039 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block MinSLEM 0.9715913534866777 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block MinResist 0.9652615861028917 No operators provided, using default LipschitzStronglyMonotoneOperator 3-Block getMaxConnectivity 0.9725788339976896 No operators provided, using default LipschitzStronglyMonotoneOperator
3-Block Min |Z-W| 0.9726116359681148 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block MinSLEM 0.964167231438586 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block MinResist 0.9664039037809664 No operators provided, using default LipschitzStronglyMonotoneOperator 2-Block getMaxConnectivity 0.9642023236838992 No operators provided, using default LipschitzStronglyMonotoneOperator
2-Block Min |Z-W| 0.9664039049575305 25
No operators provided, using default LipschitzStronglyMonotoneOperator Full 0.9626284123298885 No operators provided, using default LipschitzStronglyMonotoneOperator
MT 0.9979798028064245 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block MinSLEM 0.9811923651156044 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block MinResist 0.9738455481401165 No operators provided, using default LipschitzStronglyMonotoneOperator 5-Block getMaxConnectivity 0.9805674621972678 No operators provided, using default LipschitzStronglyMonotoneOperator
5-Block Min |Z-W| 0.9784107033253034
# Figure 9 Class 2
#projdf = pd.read_csv("figs/taus_proj.csv")
projdf[projdf["obj"].isin(["MinResist", "Full", "MT"])].groupby(['obj', 'blocks'])['tau'].plot(marker='o', linestyle='-', figsize=(10, 6))
keys = ['Full', 'MT', '2-Block', '3-Block', '4-Block', '5-Block', '6-Block', '7-Block', '8-Block', '9-Block', '10-Block', '11-Block', '12-Block'] # If using df directly
plt.legend(keys, bbox_to_anchor=(1, 1))
plt.title("Min Resistance Contraction over $n-1$ Lipschitz Strongly Monotone Operators")
plt.savefig("figs/fig_block_count_proj.pdf", format="pdf", bbox_inches="tight")
Figure 10 combines the iteration time and contraction factor to depict how removing edges impacts algorithm design. We see that the 2-Block design strikes the optimal balance between connectivity (for faster contraction) and sparseness (for parallelism and faster iteration times)
This uses the getCycleTime function to return the iteration time.
# Figure 10 - pareto curves
# 04_21_24_full_pareto.ipynb
from matplotlib.colors import CenteredNorm
def getTaus(Z, W, l=None, mu=None):
M = getMfromWCholesky(W)
h = getReducedContractionFactor(Z, M, l, mu, gamma=0.5)
m = getReducedGamma(Z, M, l, mu)[1]
return h, m
def getContractTime(n, l, mu, objective=None, tol=0.5):
Z_fixed = {}
t = np.ones(n)
ll = np.ones((n,n))
results = {}
for i in range(n//2):
print(i)
start = 0
for k in range(2):
for j in range(start, i + k*(n//2)):
Z_fixed[(i + k*(n//2),j)] = 0
Zs, Ws = objective(n, fixed_Z=Z_fixed)
h, m = getTaus(Zs, Ws, l, mu)
tt, _, _ = getCycleTime(t, ll, Zs, Ws, itrs=2)
# r is number of entries in Z_fixed
r = len(Z_fixed)
tif = np.ceil(np.log(tol)/np.log(h)) # Total iterations fixed
tio = np.ceil(np.log(tol)/np.log(m)) # Total iterations opt step
ttf = tif*tt
tto = tio*tt
results[r] = {'Fixed':h , 'M Opt': m, 'Time': tt, 'Removed Edges': r, 'Fixed Total Iterations': tif, 'Opt Step Total Iterations': tio, 'Fixed Total Time': ttf, 'Opt Step Total Time': tto}
print(results[r])
start = n//2
counter = 0
for i in range(n//2 - 2):
for j in range(i+1):
r = n//2 + j
c = n//2 - 1 - i + j
Z_fixed[(r, c)] = 0
# print(r,c)
counter += 1
if counter % 10 == 0:
Ls, Ws = objective(n, fixed_Z=Z_fixed)
h, m = getTaus(Ls, Ws, l, mu)
tt = 4
# r is number of entries in Z_fixed
rem = len(Z_fixed)
tif = np.ceil(np.log(tol)/np.log(h)) # Total iterations fixed
tio = np.ceil(np.log(tol)/np.log(m)) # Total iterations opt step
ttf = tif*tt
tto = tio*tt
results[rem] = {'Fixed':h , 'M Opt': m, 'Time': tt, 'Removed Edges': rem, 'Fixed Total Iterations': tif, 'Opt Step Total Iterations': tio, 'Fixed Total Time': ttf, 'Opt Step Total Time': tto}
print(results[rem])
# Create dataframe of taus and times
df = pd.DataFrame(results)
return df
# Figure 10
n = 24
l = np.ones(n)*2
l[n-1] = np.inf
mu = np.ones(n)
mu[n-1]= 0
df = getContractTime(n, l, mu, objective=getMaxConnectivity)
df2 = df.T
0
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9798415277932965, 'M Opt': 0.9610519693854286, 'Time': 47.99999999999555, 'Removed Edges': 0, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1679.9999999998442, 'Opt Step Total Time': 863.99999999992}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9798415277932965, 'M Opt': 0.9610519693854286, 'Time': 47.99999999999555, 'Removed Edges': 0, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1679.9999999998442, 'Opt Step Total Time': 863.99999999992}
1
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9802934213873657, 'M Opt': 0.9611344883825657, 'Time': 46.00000000002653, 'Removed Edges': 1, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1610.0000000009286, 'Opt Step Total Time': 828.0000000004776}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9802906547272658, 'M Opt': 0.9612008911749754, 'Time': 44.00000000001398, 'Removed Edges': 2, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1540.0000000004893, 'Opt Step Total Time': 792.0000000002517}
2
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803115290951551, 'M Opt': 0.9612841961043996, 'Time': 41.99999999999353, 'Removed Edges': 4, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1469.9999999997735, 'Opt Step Total Time': 755.9999999998835}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803217939995267, 'M Opt': 0.9613404324143697, 'Time': 40.00000000033539, 'Removed Edges': 6, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1400.0000000117386, 'Opt Step Total Time': 720.000000006037}
3
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803594772176855, 'M Opt': 0.9614511688616295, 'Time': 38.00000000019667, 'Removed Edges': 9, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1330.0000000068835, 'Opt Step Total Time': 684.0000000035401}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.980372539636585, 'M Opt': 0.9615160720131097, 'Time': 36.00000000005644, 'Removed Edges': 12, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1260.0000000019754, 'Opt Step Total Time': 648.0000000010159}
4
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9804160660741573, 'M Opt': 0.9616399278912013, 'Time': 34.00000000000092, 'Removed Edges': 16, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1224.000000000033, 'Opt Step Total Time': 612.0000000000165}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9803160087576462, 'M Opt': 0.9616502219370228, 'Time': 32.00000000018983, 'Removed Edges': 20, 'Fixed Total Iterations': 35.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1120.000000006644, 'Opt Step Total Time': 576.000000003417}
5
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805064379875331, 'M Opt': 0.961814464869611, 'Time': 29.999999999934413, 'Removed Edges': 25, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1079.999999997639, 'Opt Step Total Time': 539.9999999988195}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805369849158657, 'M Opt': 0.9618911233993571, 'Time': 28.000000000015866, 'Removed Edges': 30, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 1008.0000000005712, 'Opt Step Total Time': 504.0000000002856}
6
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805587441177257, 'M Opt': 0.9619696358597921, 'Time': 26.000000000192202, 'Removed Edges': 36, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 936.0000000069192, 'Opt Step Total Time': 468.0000000034596}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.980616569578718, 'M Opt': 0.9620812351430117, 'Time': 23.9999999999246, 'Removed Edges': 42, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 18.0, 'Fixed Total Time': 863.9999999972856, 'Opt Step Total Time': 431.9999999986428}
7
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9805803035541303, 'M Opt': 0.9622244218627922, 'Time': 22.000000000001247, 'Removed Edges': 49, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 792.0000000000449, 'Opt Step Total Time': 418.0000000000237}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9806097718667652, 'M Opt': 0.962304209896036, 'Time': 19.99999999987995, 'Removed Edges': 56, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 719.9999999956782, 'Opt Step Total Time': 379.99999999771904}
8
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9806706661849034, 'M Opt': 0.9624258907775105, 'Time': 17.999999999943523, 'Removed Edges': 64, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 647.9999999979668, 'Opt Step Total Time': 341.9999999989269}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9807015913368081, 'M Opt': 0.9624910820032222, 'Time': 15.999999999994685, 'Removed Edges': 72, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 575.9999999998087, 'Opt Step Total Time': 303.99999999989905}
9
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9808093208404102, 'M Opt': 0.9627105025485819, 'Time': 14.000000000000364, 'Removed Edges': 81, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 504.00000000001313, 'Opt Step Total Time': 266.00000000000693}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9808410860902486, 'M Opt': 0.9627679103016183, 'Time': 11.9999999999999, 'Removed Edges': 90, 'Fixed Total Iterations': 36.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 431.9999999999964, 'Opt Step Total Time': 227.99999999999812}
10
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9810230598007482, 'M Opt': 0.9630429010126391, 'Time': 10.000000000165418, 'Removed Edges': 100, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 370.00000000612044, 'Opt Step Total Time': 190.00000000314293}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9810393061934247, 'M Opt': 0.9630413776592525, 'Time': 7.999999999999933, 'Removed Edges': 110, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 19.0, 'Fixed Total Time': 295.99999999999756, 'Opt Step Total Time': 151.99999999999872}
11
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.981364177730722, 'M Opt': 0.9642038633941726, 'Time': 3.999999999999991, 'Removed Edges': 121, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 147.99999999999966, 'Opt Step Total Time': 79.99999999999983}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.981365178730152, 'M Opt': 0.9642023236908612, 'Time': 3.999999999999991, 'Removed Edges': 132, 'Fixed Total Iterations': 37.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 147.99999999999966, 'Opt Step Total Time': 79.99999999999983}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9838400144307651, 'M Opt': 0.9652843389466005, 'Time': 4, 'Removed Edges': 142, 'Fixed Total Iterations': 43.0, 'Opt Step Total Iterations': 20.0, 'Fixed Total Time': 172.0, 'Opt Step Total Time': 80.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9853883455134209, 'M Opt': 0.966900228979608, 'Time': 4, 'Removed Edges': 152, 'Fixed Total Iterations': 48.0, 'Opt Step Total Iterations': 21.0, 'Fixed Total Time': 192.0, 'Opt Step Total Time': 84.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9868013536962403, 'M Opt': 0.9686471381342026, 'Time': 4, 'Removed Edges': 162, 'Fixed Total Iterations': 53.0, 'Opt Step Total Iterations': 22.0, 'Fixed Total Time': 212.0, 'Opt Step Total Time': 88.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9886689488722984, 'M Opt': 0.9699045174130262, 'Time': 4, 'Removed Edges': 172, 'Fixed Total Iterations': 61.0, 'Opt Step Total Iterations': 23.0, 'Fixed Total Time': 244.0, 'Opt Step Total Time': 92.0}
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator
{'Fixed': 0.9912681529407553, 'M Opt': 0.9724134559398137, 'Time': 4, 'Removed Edges': 182, 'Fixed Total Iterations': 80.0, 'Opt Step Total Iterations': 25.0, 'Fixed Total Time': 320.0, 'Opt Step Total Time': 100.0}
df.to_csv('figs/n24.csv', index=False)
# df = pd.read_csv("figs/n24.csv")
# Plot total time vs removed edges
plt.plot(df.iloc[3], df.iloc[6], df.iloc[3], df.iloc[7])
# Subtitle
plt.suptitle('Time Units to 0.5 Contraction vs Removed Edges, $n=$'+str(n))
plt.legend( ['Fixed Step Size', 'Optimal Step Size'])
plt.xlabel('Removed Edges')
plt.ylabel('Time Units')
plt.savefig("figs/fig_optimal_sparsity.pdf", format="pdf", bbox_inches="tight")
plt.show()
# Figure 10
# Plot the top three rows of df as a function of time with points annotated
plt.plot(df.iloc[2], df.iloc[0], marker='<')
plt.plot(df.iloc[2], df.iloc[1], marker='<')
plt.title('Contraction vs Time as Edges are Removed')
# Add legend
plt.legend( ['Fixed Step Size', 'Optimal Step Size'])
# Annotate points with number of removed edges
lx, ly = (0,0)
right = 0
up = 10
for j in range(len(df.columns)):
print(j,(df.iloc[2,j], df.iloc[1,j]))
if df.iloc[2,j] < 4:
right = 10
up = 1
if df.iloc[2,j] == 4.0:
up = 0
if abs(lx - df.iloc[2,j]) > 1 or abs(ly - df.iloc[1,j]) > 0.001:
plt.annotate(df.columns[j], (df.iloc[2,j], df.iloc[0,j]), textcoords="offset points", xytext=(right,up), ha='center', fontsize=8)
plt.annotate(df.columns[j], (df.iloc[2,j], df.iloc[1,j]), textcoords="offset points", xytext=(right,up), ha='center', fontsize=8)
lx = df.iloc[2,j]
ly = df.iloc[1,j]
# Annotate with points
plt.xlabel('Average Iteration Time')
plt.ylabel(r'Contraction Rate ($\tau$)')
plt.savefig("figs/fig_pareto.pdf", format="pdf", bbox_inches="tight")
plt.show()
0 (47.99999999999555, 0.9610519693854286) 1 (46.00000000002653, 0.9611344883825657) 2 (44.00000000001398, 0.9612008911749754) 3 (41.99999999999353, 0.9612841961043996) 4 (40.00000000033539, 0.9613404324143697) 5 (38.00000000019667, 0.9614511688616295) 6 (36.00000000005644, 0.9615160720131097) 7 (34.00000000000092, 0.9616399278912013) 8 (32.00000000018983, 0.9616502219370228) 9 (29.999999999934413, 0.961814464869611) 10 (28.000000000015866, 0.9618911233993571) 11 (26.000000000192202, 0.9619696358597921) 12 (23.9999999999246, 0.9620812351430117) 13 (22.000000000001247, 0.9622244218627922) 14 (19.99999999987995, 0.962304209896036) 15 (17.999999999943523, 0.9624258907775105) 16 (15.999999999994685, 0.9624910820032222) 17 (14.000000000000364, 0.9627105025485819) 18 (11.9999999999999, 0.9627679103016183) 19 (10.000000000165418, 0.9630429010126391) 20 (7.999999999999933, 0.9630413776592525) 21 (3.999999999999991, 0.9642038633941726) 22 (3.999999999999991, 0.9642023236908612) 23 (4.0, 0.9652843389466005) 24 (4.0, 0.966900228979608) 25 (4.0, 0.9686471381342026) 26 (4.0, 0.9699045174130262) 27 (4.0, 0.9724134559398137)
Figure 11 just shows how we removed the edges
# Figure 11 - edge deletion ordering
# 04_21_24_full_pareto.ipynb
def cplot(M, c, title=''):
vmin = 1
vmax = np.max(ordermat)
cm = plt.cm.viridis #coolwarm
fig, ax = plt.subplots(1, 1, figsize=(12, 6))
x = np.arange(n)
y = -np.arange(n)
pc = ax.pcolormesh(x, y, M, cmap=cm , vmin=vmin, vmax=vmax)
ax.set_title(title) #'Edge Removal Ordering'
ax.axis('off')
ax.set_aspect('equal')
# Add colorbar
plt.tight_layout()
cbar = fig.colorbar(pc)
cbar.set_ticks(np.arange(1, c, 4))
return fig
# Display edge removal ordering
def order_graph(n):
order_matrix = np.zeros((n,n))
counter = 1
for i in range(n//2):
start = 0
for k in range(2):
for j in range(start, i + k*(n//2)):
r = i + k*(n//2)
c = j
order_matrix[(r,j)] = counter
order_matrix[(c,r)] = counter
counter += 1
start = n//2
ccounter = 0
for i in range(n//2 - 2):
for j in range(i+1):
r = n//2 + j
c = n//2 - 1 - i + j
order_matrix[(r, c)] = counter
order_matrix[(c, r)] = counter
ccounter += 1
if ccounter % 10 == 0:
counter += 1
return order_matrix, counter
ordermat, c = order_graph(24)
ordermat = np.ma.masked_array(ordermat, ordermat < 1)
fig = cplot(ordermat, c, 'Edge Removal Ordering')
fig.savefig("figs/fig_edge_removal.pdf")
Figure 12 then combines the iteration time and contraction factor to find the total time required for a given contraction level, and compares the 2-Block design with the constrained minimum iteration time design, using the minimum total effective resistance objective for each.
It demonstrates some additional parameters in the getMinCycle function. minW=n//2 sets the minimum number of edges for each node in the graph of $W$ to be $\frac{n}{2}$, which we call the constrained minimum iteration time design.
We also introduce the getMetrics function, which returns the iteration time, contraction factor, total cycles, and total time for a given contraction target, over a given design ($Z, W$), compute and communication times ($t, l$), and operator parameters (using the default values in Class 1).
# Figure 12
block_results = []
min_results = []
for n in range(6,10):
for i in range(40):
t = np.random.rand(n)*10+1
# Communication time
l = np.random.rand(n, n)*1.5 + 0.5
l = np.tril(l, -1) + np.tril(l, -1).T
Zb, Wb = getBlockMin(n, n//2, objective=getMinResist)
c, tau, cc, tt = getMetrics(Zb, Wb, t, l,contraction_target=0.01)
block_results.append((n, i, c, tau, cc, tt))
Z, W = getMinCycle(n, objective=getMinResist, t=t, l=l, c=0.01, r=n, minW=n//2)
if Z is not None:
c, tau, cc, ttc = getMetrics(Z, W, t, l,contraction_target=0.01)
else:
c, tau, cc, ttc = (None, None, None, None)
min_results.append((n, i, c, tau, cc, ttc))
print(n,i,tt,ttc)
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 0 557.3531756387047 557.3531756387047
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 1 618.6495759991482 522.5575943515803
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 2 634.3218614903401 634.3218614903401
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 3 641.4972132053769 641.4972132053769
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 4 698.1699747774383 698.1699747774383
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 5 569.515050838532 569.515050838532
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 6 376.9690001044985 376.9690001044985
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 7 670.5283718479254 670.5283718479254
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 8 507.01508244742433 507.01508244742433
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 9 611.8972113276575 611.8972113276575
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 10 515.4564016623426 515.4564016623426
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 11 352.0906040555003 352.0906040555003
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 12 680.7878167672559 574.9216073169277
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 13 681.9161056083263 681.9161056083263
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 14 438.6224794087684 379.782237023701
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 15 469.9423249042196 469.9423249042196
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 16 402.9427894920025 402.9427894920025
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 17 449.5968783117114 449.5968783117114
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 18 631.2345788947955 631.2345788947955
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 19 687.8450367311013 687.8450367311013
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 20 584.4949444173751 584.4949444173751
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 21 558.0322472678686 558.0322472678686
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 22 646.9648993960004 447.35087379702185
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 23 574.2226850876073 574.2226850876073
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 24 535.5991330142116 535.5991330142116
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 25 671.5533664181501 586.7247247959613
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 26 639.556728748259 550.1469009686596
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 27 576.6433913510302 502.9007834235641
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 28 466.0642505231957 466.0642505231957
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 29 391.35156144266284 391.35156144266284
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 30 641.0226077756681 502.83716644362454
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 31 536.7520175141719 434.8958176080492
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 32 622.749991390554 622.749991390554
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 33 697.1623001438152 590.4176839105232
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 34 715.8345026940582 715.8345026940582
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 35 391.3247675479266 320.9993232783132
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 36 693.0730278000117 693.0730278000117
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 37 493.0795606995162 493.0795606995162
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 38 642.2496924335782 642.2496924335782
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 6 39 599.9964444890811 480.4773703561166
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 0 1009.7815502095045 623.4558572405037
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 1 1201.8065590682431 843.5666502620925
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 2 1145.6308131959015 859.5487455351755
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 3 947.4243044848237 713.1464291507109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 4 920.8715257245128 642.1624468584259
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 5 655.1522775740241 802.2272786490657
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 6 1134.1154005209337 801.3685291961183
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 7 879.6441339560961 630.507661225084
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 8 1091.5053013834986 801.9222622444554
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 9 964.291619336055 637.1228731274556
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 10 1153.956774454247 858.2519390280017
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 11 890.2875453601291 672.2579424198811
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 12 1096.2046903002793 715.9773486051874
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 13 1070.5345343515824 778.811978080118
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 14 1035.5370276507733 846.687221736514
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 15 842.6281977445385 556.1096599226321
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 16 912.5942510067605 650.3648764610027
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 17 824.7190175821274 762.232543308557
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 18 969.228435560242 648.9540203521324
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 19 914.1653817607349 817.1828461036378
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 20 965.2400815544374 709.1555036140071
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 21 1156.7626981094122 875.6651395475794
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 22 1028.7596831480432 755.8234406809379
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 23 1094.0323711256517 735.8977759921172
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 24 987.7113435932681 877.2977972245396
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 25 1027.2736179436215 766.6698300592236
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 26 1057.7269452834619 813.4167944094968
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 27 977.4607632692446 836.4638762127402
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 28 791.9518623611318 547.2774913509172
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 29 998.9606350146001 750.1787685278255
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 30 981.6537449328875 741.2487461769741
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 31 1158.0924631019589 769.9113371318736
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 32 956.3123962294344 700.507671237666
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 33 761.0811635510308 515.5482941855594
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 34 796.6594732631575 598.2701796150238
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 35 1082.936177156431 796.8686706328905
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 36 887.6253880272725 614.2798370554196
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 37 1153.9034714510924 1023.530182114337
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 38 820.2557109131238 770.0359739014427
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 7 39 936.4046944131035 811.3183457179131
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 0 778.3397473458791 778.3397473458791
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 1 931.3660108877552 931.3660108877552
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 2 908.4394300816159 908.4394300816159
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 3 1041.3379427886944 856.3930519515962
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 4 871.4342775781261 871.4342775781261
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 5 850.6989835614263 670.9498570762278
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 6 887.3557897689439 887.3557897689439
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 7 920.8772236131991 920.8772236131991
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 8 943.7214241050503 943.7214241050503
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 9 987.6096517203971 845.8357282580005
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 10 875.6381419983431 722.2454910197346
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 11 986.322043729115 986.322043729115
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 12 861.6899111945168 720.1562322940163
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 13 788.7211125229427 788.7211125229427
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 14 917.2799372835626 917.2799372835626
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 15 944.0450336283072 944.0450336283072
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 16 906.1056960434966 755.5509489068345
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 17 971.1858977012915 971.1858977012915
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 18 1010.9826696179744 1010.9826696179744
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 19 973.7568330509746 973.7568330509746
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 20 758.1515803222592 706.1069606299252
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 21 956.9002336963649 884.2695705966117
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 22 917.1738005707653 917.1738005707653
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 23 611.5636068897693 611.5636068897693
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 24 947.3587883796454 947.3587883796454
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 25 959.6749501212437 959.6749501212437
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 26 798.642723049982 798.642723049982
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 27 755.2356205115374 680.2153843515109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 28 871.6707451189536 871.6707451189536
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 29 1011.0537713146791 1011.0537713146791
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 30 949.0195830383495 719.6255055421284
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 31 818.3700512676226 818.3700512676226
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 32 987.6596784885056 987.6596784885056
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 33 904.6457929185774 904.6457929185774
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 34 781.7442794868281 734.6786220698642
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 35 721.8061592582985 628.4237756294692
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 36 839.0214391230143 839.0214391230143
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 37 973.9200485594929 973.9200485594929
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 38 895.0188088120344 895.0188088120344
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 8 39 783.8552945310688 613.4379259997809
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 0 1254.3220674725992 906.7988521573361
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 1 1276.351145350438 997.1872254269489
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 2 1116.1432991760576 878.2766944428877
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 3 1418.989552484359 1015.0759854496991
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 4 1191.6506624970289 1523.7500301935197
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 5 1391.810325126577 1095.1950099327642
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 6 1316.1890348950299 980.5058682022782
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 7 1530.9143631044203 919.1728272512466
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 8 1389.2737931499328 1093.1990503867291
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 9 1230.8809460978837 867.0100337855438
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 10 1173.5241369254095 849.7477488078184
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 11 1378.1317049542104 953.8722803054234
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 12 1163.894999712936 896.7715576115384
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 13 1275.4440953218545 980.9006570250478
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 14 1398.2278631972194 1003.0954761348794
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 15 1050.7988297568377 600.7778510931678
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 16 1011.421738391258 1077.7444749856534
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 17 1368.6247759961773 1058.5034933550446
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 18 1232.035399371981 865.966429542229
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 19 1321.1751054851338 1277.8578884005497
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 20 1448.3797976146698 1017.3230403319209
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 21 1439.708013196225 1080.562288192114
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 22 1216.6704131775964 884.5922371129849
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 23 1348.93208071445 996.9290304282686
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 24 1264.5398888907396 800.8907987028069
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 25 1440.0590426928093 929.814586081895
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 26 1418.1136400332998 831.4045368645209
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 27 1248.1736047928566 967.559049199994
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 28 1243.1472587309083 1073.5042143858855
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 29 1354.019138928614 1065.4576831171744
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 30 1292.997356682974 771.5855441536868
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 31 1341.8157971282185 972.3020323513883
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 32 1541.8228632480113 1039.2316369260504
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 33 766.3023077543863 979.8619674361797
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 34 1385.6760107130713 1340.244010308109
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 35 1398.588412707733 1042.228782007279
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 36 1412.6165398163778 1024.4818313434662
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 37 1163.4922838390758 840.8499359932923
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 38 1317.6194293430312 904.2595731915733
No operators provided, using default LipschitzStronglyMonotoneOperator
No operators provided, using default LipschitzStronglyMonotoneOperator 9 39 1092.0057622338984 800.2356482873975
# Figure 12
block_df = pd.DataFrame(block_results)
min_df = pd.DataFrame(min_results)
block_df.to_csv('figs/block_df2.csv')
min_df.to_csv('figs/min_cycle_min_edge.csv')
# Paired density chart for block vs min cycle
# Figure 12
# block_df = pd.read_csv('figs/block_df2.csv')
# min_df = pd.read_csv('figs/min_cycle_min_edge.csv')
fig, axs = plt.subplots(2, 2, sharey=True)
n = 6
key = 5 #'5' #use string if loading from csv
start = 0
for i in range(2):
for j in range(2):
end = 40 + start
axs[i,j] = block_df[key][start:end].plot.kde(ax=axs[i,j], color='blue')
min_df[key][start:end].plot.kde(ax=axs[i,j], color='red')
start += 40
axs[i,j].set_title(r"$n=$"+str(n))
n += 1
fig.legend([r'$d$-Block Design', 'Con. Min Iter Time'], loc=(.65,.8))
for ax in axs.flat:
ax.set(xlabel='Time')
for ax in fig.get_axes():
ax.label_outer()
fig.savefig("figs/fig_constrained_mincycle_histogram.pdf", format="pdf", bbox_inches="tight")